FM算法原文。

论文背景

　　2010 IEEE International Conference on Data Mining
　　Steffen Rendle
　　Department of Reasoning for Intelligence
　　The Institute of Scientific and Industrial Research Osaka University, Japan
谷歌学术被引用次数1396（截至2020年12月14日）
　　论文关键词：factorization machine; sparse data; tensor factorization; support vector machine
　　PDF

Introduction 引言

　　FM优点：
　1. FM能在很稀疏的数据上进行参数估计，但SVM不行。
　2. FM是线性复杂度，不需要类似于SVM中的支持向量。
　3. FM是通用预测方法，适用于任何特征向量。其它的因子分解方法都受限于特定的输入。（对比biased MF, SVD++, PITF和FPMC）

Prediction under sparsity 稀疏情况下的预测

Factorization machines(FM) 因子分解机

Factorization machine model 因子分解机模型

　　degree d = 2
$$\hat{y}(x):=w_0 + \sum_{i=1}^nw_ix_i + \sum_{i=1}^n\sum_{j=i+1}^n<v_i,v_j>x_ix_j$$
　　其中$w_0∈R$，$w∈R^n$,$V∈R^{n×k}$，<·,·>表示点乘。
$$<v_i,v_j>:=\sum_{f=1}^kv_{i,f}·v_{j,f}$$
　　V中的$v_i$描述k个因素中的第i个变量。$Ks∈N_0^+$是定义因子分解的维度的超参数。
　　2-way FM捕捉所有变量的单个和成对交互：
　　$w_0$是全局偏置，$w_i$模拟了第i个变量的程度。
　　$\hat{w}_{i,j}:=<v_i, v_j>$模拟了第i和第j个变量间的交互。这个在高阶交互时（d > 2）高质量估计的关键。
　　时间复杂度O($kn^2$)，因为所有的交互对都要被计算。但可以变形使之化为O(kn)。

Factorization machines as predictors FM作为预测器

　　可用于回归、二分类和排序问题。

Learning factorization machines FM学习策略

　　使用随机梯度下降（SGD）来学习。

d-way factorization machine 多维FM

　　同时2-way FM可以拓展为d-way。

Summary 总结

　　FM优点：
　　1. 在高稀疏下可估计特征交互，尤其是不可观测的交互。
　　2. 预测和学习的时间复杂度是线性的。使SGD优化可行，并允许多种损失函数优化。

FMs vs. SVMs 因子分解机对比支持向量机

SVM model 支持向量机模型

　　SVM等式$$\hat{y}(x) = <\Phi(x), w>$$
　　其中$\Phi$是从空间$R^n$到F的映射。$\Phi$和下式的核相关：
$$K:R^n × R^n → R, K(x, z) = <\Phi(x), \Phi(z)>$$
1) 线性核
　　$K_l(x, z) = 1 + <x, z>$，对应$\Phi(x) := (1, x_1, … , x_n)$
　　SVM等式为
$$\hat{y}(x) = w_0 + \sum^n_{i=1}w_ix_i, w_0∈R, w∈R^n$$
　　这等价于FM中d = 1的情况。

2) 多项式核
　　多项式核使SVM能模拟变量间的高阶交互。
$K(x, z) := (<x, z> + 1)^d$，对于d = 2有
$\Phi(x) := (1, \sqrt{2}x_1, … , \sqrt{2}x_n, x_1^2, … , x_n^2, \sqrt{2} x_1x_2, … , \sqrt{2}x_1x_n, \sqrt{2}x_2x_3, … , \sqrt{2}x_{n-1}x_n$
　　SVM等式为
$$\hat{y}(x) = w_0 + \sqrt{2}\sum^n_{i=1}w_ix_i + \sum^n_{i = 1}w_{i,i}^{(2)}x_i^2 + \sqrt{2}\sum^n_{i=1}\sum^n_{j=i+1}w_{i,j}^{(2)}x_ix_j$$
　　其中$w_0∈R, w∈R^n, w^(2)∈R^{n×n}$。
　　d = 2时，FM和SVM的区别在于SVM中$w_{i,j}$是完全独立的，而FM中参数是因子分解的，所以$<v_i, v_j>$依赖于彼此。

Parameter Estimation Under Sparsity 在稀疏情况下的参数估计

　　举例：使用协同过滤（上图中蓝色和红色部分数据）。
1) 线性SVM
$$\hat{y}(x) = w_0 + w_u + w_i$$
　　只有j = u 或 j = i时$x_j$ = 1，即只有用户和物品偏好被选中时才有用。由于模型简单，在稀疏情况也能进不错的参数估计，但预测质量低。
2) 多项式SVM
$$\hat{y}(x) = w_0 + \sqrt{2}(w_u + w_i) + w_{u,u}^{(2)} + w_{i,i}^{(2)} + \sqrt{2}w_{u,i}^{(2)}$$
　　$w_u$和$w_{u,u}^{(2)}$是一样的。该等式除了一个额外的$w_{u,i}$，等价于线性SVM。在训练集中，对于每一个$w_{u,i}$最多只有一条记录，在测试集中通常没有。因此，2-way的SVM效果也不比线性SVM好。

Summary 总结

1) SVM需要直接观测交互数据，但稀疏数据集经常没有。FM参数可以在系数情况下进行不错的参数估计。
2) FM可以一开始就直接学习，但非线性SVM需要成对学习。
3) FM是独立于训练集的，SVM的预测是基于部分训练数据的。

FMs VS. Other Factorization Models 其它因子分解方法对比

　　改写FM公式形式，分别与Matrix and Tensor Factorization矩阵和张量分解、SVD++、PITF for Tag Recommendation、Factorized Personalized Markov Chains(FPMC)方法对比，FM改写后性能与这些方法实现效果类似。

Summary 总结

1) 标准因子分解模型（比如PARAFAC或者MF）不像FM一样是通用预测模型。
2) 修改特征提取部分，FM可以模拟在特定任务下的成功模型（比如MF,PARAFAC,SVD++,PITF,FPMC)。

Conclusion and Future Work 总结和展望

　　与SVM对比，
1) 在数据稀疏情况下，FM可以进行参数估计。
2) 模型时间复杂度是线性的，并且只依赖于模型参数。
3) 从最开始就能直接优化。